1. Field
Example aspects of the invention relate to a procedure, system, apparatus, and program for allocating network bandwidth in a Max-Min fair manner, and, in particular, to bandwidth allocation using breakpoints based on tiers formed by grouping users according to maximum allocation information.
2. Related Art
In the highly-connected computing environments of the present day, multiple users often must share a limited computing resource. If total user demand for a shared resource exceeds the amount of resource available, the resource must be apportioned among the users. In the field of computer networking, for example, many methods have been developed to allocate shared network bandwidth to users in a fair and/or efficient manner. In particular, some bandwidth allocation systems apportion available bandwidth among competing users over an interval of time such that Max-Min fairness is achieved.
Max-Min fairness (MMF) is a well-known fairness objective that describes an end result of an allocation of a quantity of resources among a set of competing users. Specifically, as a result of a Max-Min fair allocation of an available resource, the resource allocation between two users is equal (or is in a ratio equal to the ratio of users' weights in a weighted Max-Min fairness system), except that each user's allocation is also subject to a respective maximum allocation. However, Max-Min fairness is a principle whose definition is not “constructive.” In other words, while the principle of MMF provides an objective end result of an allocation, MMF definition does not provide a method to achieve this final allocation.
Some existing approaches to designing a method to achieve MMF allocation of available bandwidth are both computationally inefficient and inexact. For example, one approach is to cycle through the users, providing each with a small unit of bandwidth allocation during each iteration, but bypassing any user whose net allocation has reached its maximum. This approach is inefficient because it is likely to involve a large number of iterations, each of which involves memory accesses, comparisons with a user's maximum allocation, and arithmetic operations to increment the allocation. This approach is also inexact, since it is limited in precision by the size of the unit of bandwidth allocation.